from collections import defaultdict
from typing import List


class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        edges = defaultdict(list)
        for i, j in enumerate(parent):
            edges[j].append(i)
        self.ans = 1

        def dfs(node: int) -> int:
            """
            :param node:
            :return: 所有子树的最长路径
            """
            roads = []
            length = 1
            for next_ in edges[node]:
                val = dfs(next_)
                if s[next_] != s[node]:
                    roads.append(val)
            roads.sort()
            if len(roads) >= 2:
                self.ans = max(self.ans, 1 + roads[-1] + roads[-2])
            if len(roads) >= 1:
                self.ans = max(self.ans, 1 + roads[-1])
                length = roads[-1] + 1
            return length

        dfs(0)
        return self.ans


if __name__ == '__main__':
    s = Solution()
    r = s.longestPath([-1], 'z')
    print(r)
